/**
 * 判断链表是否有环
 */
public class Main {

    public static void main(String[] args) {
        ListNode node2 = new ListNode(2,null);
        ListNode node1=new ListNode(1,node2);
        System.out.println(hasCycle(node1));
    }

    public static boolean hasCycle(ListNode head) {
        if (head==null || head.next==null){
            return false;
        }
        //定义快慢指针，快指针每次走两个，慢指针每次走一个，如果二者相遇，说明有环（若无环则快的永远在慢的前面，不会相遇）
        ListNode fast = head;
        ListNode slow = head;
        while (slow!=null && fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                //二者相遇，说明有环
                return true;
            }
        }
        return false;
    }

    /**
     * 链表中的节点类
     */
    static class ListNode{
        int value;
        ListNode next;

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

}

